#include <inttypes.h>
uint16_t lookup[] = {
5000,
5104,
5209,
5313,
5418,
5522,
5626,
5730,
5833,
5936,
6039,
6141,
6243,
6344,
6445,
6545,
6644,
6742,
6840,
6937,
7033,
7128,
7223,
7316,
7408,
7500,
7590,
7679,
7766,
7853,
7938,
8022,
8105,
8187,
8267,
8345,
8422,
8498,
8572,
8644,
8715,
8784,
8852,
8918,
8982,
9045,
9105,
9164,
9221,
9276,
9330,
9381,
9431,
9478,
9524,
9567,
9609,
9648,
9686,
9721,
9755,
9786,
9815,
9842,
9867,
9890,
9911,
9929,
9946,
9960,
9972,
9982,
9990,
9995,
9998,
10000,
9998,
9995,
9990,
9982,
9972,
9960,
9946,
9929,
9911,
9890,
9867,
9842,
9815,
9786,
9755,
9721,
9686,
9648,
9609,
9567,
9524,
9478,
9431,
9381,
9330,
9276,
9221,
9164,
9105,
9045,
8982,
8918,
8852,
8784,
8715,
8644,
8572,
8498,
8422,
8345,
8267,
8187,
8105,
8022,
7938,
7853,
7766,
7679,
7590,
7500,
7408,
7316,
7223,
7128,
7033,
6937,
6840,
6742,
6644,
6545,
6445,
6344,
6243,
6141,
6039,
5936,
5833,
5730,
5626,
5522,
5418,
5313,
5209,
5104,
5000,
4895,
4790,
4686,
4581,
4477,
4373,
4269,
4166,
4063,
3960,
3858,
3756,
3655,
3554,
3454,
3355,
3257,
3159,
3062,
2966,
2871,
2776,
2683,
2591,
2500,
2409,
2320,
2233,
2146,
2061,
1977,
1894,
1812,
1732,
1654,
1577,
1501,
1427,
1355,
1284,
1215,
1147,
1081,
1017,
954,
894,
835,
778,
723,
669,
618,
568,
521,
475,
432,
390,
351,
313,
278,
244,
213,
184,
157,
132,
109,
88,
70,
53,
39,
27,
17,
9,
4,
1,
0,
1,
4,
9,
17,
27,
39,
53,
70,
88,
109,
132,
157,
184,
213,
244,
278,
313,
351,
390,
432,
475,
521,
568,
618,
669,
723,
778,
835,
894,
954,
1017,
1081,
1147,
1215,
1284,
1355,
1427,
1501,
1577,
1654,
1732,
1812,
1894,
1977,
2061,
2146,
2233,
2320,
2409,
2500,
2591,
2683,
2776,
2871,
2966,
3062,
3159,
3257,
3355,
3454,
3554,
3655,
3756,
3858,
3960,
4063,
4166,
4269,
4373,
4477,
4581,
4686,
4790,
4895,
};
